﻿//26. 删除有序数组中的重复项

/*思路：使用前后指针，前指针负责找和后指针指向不同的值，找到以后++后指针，把前指针指向的值给后指针，前指针再++，一直走到结束*/
int removeDuplicates(int* nums, int numsSize){
    int n=0;
    int cur=1;
    while(cur<numsSize)
    {
        if(nums[n]!=nums[cur])
        {  
           nums[++n]=nums[cur++];
        }
        else
        {
            while(cur<numsSize && nums[n]==nums[cur])//相等或者最后没找到不等的退出
            {
                cur++;
            }  

            if(cur==numsSize)  //没找到并且找到尾了
            {
                break;
            }

            nums[++n]=nums[cur++];
        }
    }
    return n+1;
}

88. 合并两个有序数组
 //nums1从后往前入数据
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){

    int end1=m-1;
    int end2=n-1;
    int end=m+n-1;
    while(end1>=0&&end2>=0)
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[end--]=nums1[end1--];
        }
        else
        {
            nums1[end--]=nums2[end2--];
        }
    }
    while(end1>=0)
    {
         nums1[end--]=nums1[end1--];
    }

     while(end2>=0)
    {
         nums1[end--]=nums2[end2--];
    }


}
//27. 移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n=0;
        
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=val)
            {
                nums[n++]=nums[i];
            }       
        }
        return n;
    }
};

//189. 轮转数组
void reverse(int* nums,int left,int right)
{
while(left<right)
{
    int tmp=0;
    tmp=nums[left];
    nums[left]=nums[right];
    nums[right]=tmp;
    left++;
    right--;
}

}
/*3次逆置（前n-k）（后k）（整体）*/ 
void rotate(int* nums, int numsSize, int k){
    k=k%numsSize;
reverse(nums,0,numsSize-k-1);
reverse(nums,numsSize-k,numsSize-1);
reverse(nums,0,numsSize-1);
}

//面试题 17.04. 消失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size=nums.size();
        int ret=0;      
        for(auto& e:nums)//先把容器里面的数据异或在一起
        {
            ret^=e;
        }
        for(int i=0;i<= size;i++)//nums包含从0到n的所有整数，再去异或从【0，n】的数，剩下的就是求的
        {
            ret^=i;
        }
        return ret;
    }
};